#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>


struct TreeNode
{
    int val;
    TreeNode *lchild;
    TreeNode *rchild;
};

bool addNode(TreeNode*&root,int val)
{
    // 先判空作为递归结束条件
    if (!root)
    {
        TreeNode*node = new TreeNode;
        node->val = val;
        node->lchild = nullptr;
        node->rchild = nullptr;
        root = node;
        return true;
    }
    else 
    {
        if (addNode(root->lchild,val))
        {
            return true;
        }
        else 
        {
            addNode(root->rchild,val);
            return true;
        }
    }
}

// 我知道了，完全二叉树可以使用数组实现，普通二叉树可以任意添加
// 那返回bool值的函数在哪里学的呢????

// 层级遍历，但是返回vector<vector<int>>
std::vector<std::vector<int>> levelOrder(TreeNode*root) 
{
    // 先判空，无论如何不能少
    std::vector<std::vector<int>>res;
    if (!root)    
    {
        return res;
    }

    // 使用队列进行自然层级遍历
    std::queue<TreeNode*>q;
    q.push(root);
    while (!q.empty())
    {
        // 获取队列大小作为上一次预先放入的这一层的大小
        int n = q.size();
        std::vector<int>layer;

        // 按照指定次数遍历队列
        while (n--)
        {
            TreeNode*temp = q.front();
            if (temp)
            {
                q.push(temp->lchild);
                q.push(temp->rchild);
                layer.push_back(temp->val);
            }
            q.pop();
        }

        // 将矩阵加入到结果中
        res.push_back(layer);
    }

    return res;
}

// 普通层级遍历实现
void level_sunui(TreeNode*root)
{
    // 第一步判空
    if (!root)
    {
        return;
    }

    // 创建队列
    std::queue<TreeNode*>q;
    q.push(root);

    // 只要队列不为空
    while (!q.empty())
    {
        // 进行遍历操作
        TreeNode*temp = q.front();
        std::cout<<temp->val<<"\n";

        // 将子节点加入队列
        if (temp->lchild)
        {
            q.push(temp->lchild);
        }
        if (temp->rchild)
        {
            q.push(temp->rchild);
        }
        q.pop();
    }
}

int main()
{
    TreeNode *root = new TreeNode;
    root->val = 3;

    TreeNode*nine = new TreeNode;
    nine->val = 9;
    nine->lchild = nullptr;
    nine->rchild = nullptr;
    root->lchild = nine;

    TreeNode*twenty = new TreeNode;
    twenty->val = 20;
    root->rchild = twenty;
    twenty->lchild = nullptr;
    twenty->rchild = nullptr;

    TreeNode*fifteen = new TreeNode;
    twenty->lchild = fifteen;
    fifteen->val = 15;
    fifteen->lchild = nullptr;
    fifteen->rchild = nullptr;

    TreeNode*seven = new TreeNode;
    twenty -> rchild = seven;
    seven->val = 7;
    seven->rchild = nullptr;
    seven->lchild = nullptr;

    // 准备开始遍历
    // 但是装入vector容器
    std::vector<std::vector<int>>res = levelOrder(root);
    for (auto v:res)
    {
        for (auto i:v)
        {
            std::cout<<i<<" ";
        }
        std::cout<<"\n";
    }

    return 0;
}